package com.myown.algorithm;

import java.util.*;

/**
 * 遗传算法解决旅行商问题 <p>
 *
 * 遗传算法的基本步骤是：
 * 1、初始化-随机选择一些个体组成最初的种群（Population），地球最原始的生命也是随机产生的。
 * 2、评估-通过某种方法来评估个体的适应度。个体的生存能力。
 * 3、选择-类似于自然选择，优良的基因（Gene）、生存能力强的被选择下来的概率要大。当然，也存在屌丝逆袭的情况。
 * 4、交叉-产生后代，基因交叉，可以理解为有性繁殖，子代会分别从父母那得到部分基因。
 * 5、变异-后代的基因可能会变异。变异在生物进化起了很大作用。 <p>
 *
 * 问题描述：
 * 旅行推销员问题（Travelling Salesman Problem，又称为旅行商问题、货郎担问题、TSP问题）是一个多局部最优的
 * 最优化问题：有n个城市，一个推销员要从其中某一个城市出发，唯一走遍所有的城市，再回到他出发的城市，求最短的路
 * 线。也即求一个最短的哈密顿回路。
 *
 * @author lincky
 * @version v1.0.0
 * @time 2017/3/26 12:27
 */

public class TSP {

    private List<City> cities;
    /**
     * 种群数量
     */
    private List<Route> routes;

    // 代数
    private int gen;
    // 交叉概率
    private double pc = 0.5;
    // 变异概率
    private double pm = 0.1;

    private static final int MAX = 100;
    private int routeNum;

    public TSP(List<City> cities, int routeNum, int gen) {
        this(cities, gen, 0.5, 0.1, routeNum);
    }

    /**
     *
     * @param cities 城市
     * @param gen 繁衍次数
     * @param pc 交叉概率
     * @param pm 变异概率
     * @param routeNum 种群规模
     */
    public TSP(List<City> cities,
               int gen,
               double pc,
               double pm,
               int routeNum) {
        this.cities = cities;
        this.gen = gen;
        this.pc = pc;
        this.pm = pm;
        this.routeNum = routeNum;
    }

    private void init() {
        routes = randomRoute(cities, routeNum);
    }

    private Route select(List<Route> routes) {
        return RandomUtil.getRandomByWeight(routes);
    }

    private Route best(List<Route> routes) {
        return Collections.max(routes);
    }

    private void evolution(Route route) {
        if (RandomUtil.p(pc)) {
            // 交叉
            cross(route);
            route.sufficiency = sufficiency(route);
        } else {
            if (RandomUtil.p(pm)) {
                // 变异
                variation(route);
                route.sufficiency = sufficiency(route);
            }
        }
    }

    public void cross(Route route) {
        int min = RandomUtil.getRandom(1, route.size() - 2);
        int max = RandomUtil.getRandom(1, route.size() - 2);
        if (min > max) {
            int temp = min;
            min = max;
            max = temp;
        }
        for (int j = min; j <= max; j++) {
            swap(route.cities, j, route.size() - j - 1);
        }
    }

    private void variation(Route route) {
        int random = RandomUtil.getRandom(1, route.size() - 2);
        swap(route.cities, random, route.size() - random - 1);
    }

    public Route find() throws CloneNotSupportedException {
        init();
        Route best = best(routes).clone();
        for (int i = 0; i < gen; i++) {
            for (int j = 0; j < routes.size(); j++) {
                Route route = select(routes);
                evolution(route);
            }
            Route temp = best(routes).clone();
            if (temp.compareTo(best) > 0) {
                best = temp;
            }
        }
        return best;
    }

    /**
     * 距离
     * @param a 城市a
     * @param b 城市b
     * @return 距离
     */
    private double distance(City a, City b){
        return Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2));
    }

    private List<City> randomCity(int n) {
        List<City> cities = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            City city = new City(i,
                    RandomUtil.getRandom(MAX),
                    RandomUtil.getRandom(MAX));
            cities.add(city);
        }
        return cities;
    }

    public List<Route> randomRoute(List<City> cities,
                                    int n) {
        List<Route> routes = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            Route route = new Route();
            route.cities = new ArrayList<>();
            route.cities.addAll(cities);
            RandomUtil.randomizeInPlace(route.cities, 1, cities.size() - 2);
            route.sufficiency = sufficiency(route);
            routes.add(route);
        }
        Collections.sort(routes);
        return routes;
    }

    private double sufficiency(Route route) {
        double distance = 0;
        for (int j = 1; j < route.cities.size(); j++) {
            distance += distance(route.cities.get(j - 1),
                    route.cities.get(j));
        }
        return distance;
    }

    public static <T> void swap(List<T> list, int a, int b) {
        T t = list.get(a);
        list.set(a, list.get(b));
        list.set(b, t);
    }

    static class City {
        int id;
        int x;
        int y;

        public City(int id, int x, int y) {
            this.id = id;
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "id=" + id;
        }
    }

    class Route implements Weight, Comparable<Route>, Cloneable {
        List<City> cities;
        double sufficiency;

        public int size() {
            return cities.size();
        }

        @Override
        public String toString() {
            return "Route{" +
                    "cities=" + cities +
                    ", sufficiency=" + sufficiency +
                    '}';
        }

        @Override
        public double weight() {
            return sufficiency;
        }

        @Override
        public int compareTo(Route o) {
            return (int) (sufficiency - o.sufficiency);
        }

        @Override
        public Route clone() throws CloneNotSupportedException {
            return (Route) super.clone();
        }
    }


}
